package sort;

import java.util.Arrays;

public class ShellSort {

  public static void main(String[] args) {
    int[] arr ={5,3,89,56,-1,6,45,7};
    shellSort(arr);
    System.out.println(Arrays.toString(arr));
  }

  public static void shellSort(int [] arr){
      for (int gap=arr.length/2;gap>0;gap/=2){
          for (int i=gap;i<arr.length;i++){

              int j=i;
              int insertVal=arr[j];
              while (j-gap>=0&&insertVal<arr[j-gap]){
                  arr[j]=arr[j-gap];
                  j-=gap;
              }
              arr[j]=insertVal;
          }
      }
  }
}
